НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №5 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «Лінійні однозв’язні та двозв’язні списки» Варіант № 15 Дата « 12 » червня 2022  Мета роботи: Метою лабораторної роботи є ознайомитися з основами роботи з двозв’язним списком, однозв’язним списком, стеком та чергою. Теоретична частина: Однозв'язний список — вид зв’язного списку, який складається з вузлів, кожен з яких містить у собі дані (інформаційну частину) та посилання на наступний вузол. / Двобічно зв'язаний список — вид зв’язного списку, у якому посилання в кожному вузлі вказують на попередній і на подальший вузол у списку. Якщо в списку після останнього елемента йде перший, то такий список називається кільцевим двобічно зв'язаним списком. Тобто, поле prev голови списку вказує на хвіст списку, а поле next хвоста списку вказує на голову списку. По двобічно зв'язаному списку можна пересуватися в будь-якому напрямку — як від початку до кінця, так і навпаки. Для нього простіше проводити видалення і перестановку елементів, оскільки завжди відомі адреси тих елементів списку, вказівник яких спрямований на змінюваний елемент. / Найчастіше вузлом списку вважають структурний тип (структуру), який зберігає у собі певну інформаційну частину (іншу структуру або тип даних) та посилання (вказівник) на наступний вузол у списку. Список має «голову», тобто вказівник на початок списку та інколи має кінець, проте найчастіше його не використовують. Мабуть найголовнішою перевагою списку є набагато зручніша робота із динамікою. Наприклад, при створенні динамічного масиву, коли місце у ньому кінчається приходиться копіювати всі елементи, свторювати новий, більший за розміром, а старий видаляти. У спискам набагато зручніше додавати нові елементи. Але в той же час, його набагато складніше контролювати у порівнянні із звичайним масивом. Стек являє собою об’єкт, робота з яким – додавання і видалення – здійснюється за принципом LIFO (last-in first-out – останнім прийшов – першим пішов). Додавання об’єктів в стек може здійснюватися в будь-який момент, видаляється ж лише об’єкт, доданий останнім. / Черга (queue) – лінійний список, у якому всі видалення відбуваються на одному кінці списку, а всі включення (і звичайно всякий доступ) робляться на іншому його кінці. Інакше кажучи, у черги є голова (head) і хвіст (tail). Елемент, що додається в чергу, виявляється в її хвості У черзі новий елемент додається тільки з одного кінця. Видалення елемента відбувається на іншому кінці. Черга (queue), це по суті однонаправлений список, тільки додавання й видалення елементів відбувається на кінцях списку. / Завдання роботи: 1. Створити лінійний однозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його, а попередній та настуні поміняти місцями. Виконати завдання згідно варіанту. 2. Створити двозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його. Виконати завдання згідно варіанту з двозвязним спмском. / Результат: Заповнити стек можна за допомогою меню, натискаючи кнопку 1 – вам запропонують ввести елемент який потрібно покласти в стек. За допомогою кнопки 2, у вас буде можливість порівняти суму від’ємних та додатніх чисел у стеку. А за допомогою клавіші 3 – ви зможете роздрукувати стек у консоль. Клавіша 0 – вихід із програми. / / Посилання на Replit: https://replit.com/join/dkxvcxvkts-tr-15fundamient Висновок: Під час виконання даної лабораторної роботи ознайомлено на практиці з роботою з однозв’язними та двозв’язними списками, стеком та чергою. У результаті виконання роботи було написано реалізацію стеку, та реалізацію завдання, відповідного до много варіанту. Усе працює згідно вимог. Копія коду: #include<iostream> #include <math.h> using namespace std; struct Node { int data; struct Node* next; }; struct Node* head; class stack { i...